The present invention relates to a cryptographic key sharing method employed in a star communication system consisting of a base station and a plurality of terminals or a communication system consisting of only a system manager and a plurality of terminals and, more particularly, a key sharing method which is capable of safely distributing a common secret key to all terminals except terminals specified by the base station, and a key sharing method which is capable of safely distributing the common secret key only to particular terminals.
In the star communication system in which the base station manages a plurality of terminals, the case is discussed where the base station and a plurality of subsidiary terminals constitute a group and then the same group secret key is shared with the group members to broadcast the cipher communication. Information encrypted by using the group secret key can be decrypted only by the terminals which have the same secret key in the group.
Meanwhile, the case where particular terminals should be excluded from this group will occur. There are cases where, for example, a certain terminal in the group is robbed and thus illegal practices such as the eavesdrop of the cipher communication, the transmission of false information, etc. are conducted by using the terminal. At this time, the base station which manages this secret key must exclude the stolen terminal as soon as possible and update the group secret key, and only remaining terminals must share a new secret key.
Also, it is necessary to construct another group newly. There are cases where the out-of-group terminal is entered into the group, the terminals which belong to different groups are combined into one group, etc. At this time, the base station must share a new group key as soon as possible with the terminals constituting the group.
FIG. 29 shows a key updating method to share the key data with terminals other than the terminals specified by the base station, according to the first example in the prior art. In FIG. 29, five terminals T1 to T5 hold inherent keys k1 to k5 respectively, and the base station manages the inherent keys of all terminals. At this time, the case where, for example, the base station excludes the terminal T1 and distributes a new common secret key to other terminals T2 to T5 will be explained hereunder.
First, the base station generates the secret key K, encrypts this secret key K by using k2 to k5 as keys respectively, and distributes them to the terminals T2 to T5 respectively. Respective terminals except the excluded terminal T1 decrypt the encrypted keys by using the inherent keys to obtain the secret key K. In FIG. 29, for example, Ek2(K) is the ciphertext which is obtained by encrypting K by using the inherent key k2. Since data on this communication line are encrypted by the inherent keys of the terminals T2 to T5 respectively, the terminal T1 cannot obtain the secret key K generated by the base station even if such terminal T1 can intercept this communication data.
However, according to this method, in order to exclude one terminal from N terminals, normally the base station must perform (Nxe2x88x921) time the encryption and transmit (Nxe2x88x921) pieces of data. If a size of the group is increased, this operation becomes extremely a burden on the base station. In addition, the services such as the cipher communication, etc. in the group must be stopped until all station have been updated. In this case, if the service suspending term which is required until distribution of data to (Nxe2x88x921) terminals has been finished is prolonged, the weighty problem has arisen.
FIG. 30 shows a key updating method, which is disclosed in Patent Application Publication (KOKOKU) Hei 5-46731, according to the second example in the prior art. In this second example in the prior art, the public key cryptosystem is employed. In FIG. 30, five terminals T1 to T5 hold intrinsic secret keys (e1, d1) to (e5, d5) respectively. Here, suppose that
eixc2x7di mod(pxe2x88x921)=1 (p is a prime number of the system publication)
can be satisfied in each secret key (ei, di). The base station 1 manages the public keys
p1=ge1 modp, . . . , p5=ge5 modp
of all terminals. Where g is an integer of the system publication. To calculate the secret key (ei, di) of each terminal based on the public key pi of each terminal and information g, p of the system publication is difficult because it arrives at the discrete logarithm problem if the bit length is set long. Like the example 1 in the prior art, if the terminal T1 should be excluded, first the base station generates a random number R and generates a key
K=gR modp
and thus calculates
Z2=p2R modp, . . . , Z5=p5R modp
and then distributes them to T2 to T5 except the terminal T1. The respective terminals i except the terminal T1 obtain the updated keys K
K=Zidi modp(=(piR)di modp=((gei)di)R modp=gR modp),
which are common to the base station, by using the received Zi and the secret key di.
However, according to the key sharing method in the prior art, in order to exclude one terminal from N terminals, the base station must perform (Nxe2x88x921) time the encryption and transmit (Nxe2x88x921) pieces of data. For example, the case will be considered where one terminal is excluded from 1000 terminals and then a new common secret key is shared with remaining 999 terminals. At this time, in the first and second examples in the prior art, the encryption process must be carried out 999 times and also 999 ciphertexts must be transmitted. At any rate, these operations put the heavy burden onto the base station side.
Further, normally the terminal has not so high computational capability since it must be implemented small in size at low cost. Such terminal must update the key at high speed. In the second example in the prior art, the terminal must perform the power residue calculation of long bit length to obtain the key. Such calculation puts the considerable burden onto the terminal which has not the high computational capability, so that the processing time becomes long until the key sharing can be achieved.
The present invention has been made in light of such points and it is an object of the present invention to achieve a key sharing method of sharing distributed key information with other terminals and a key sharing method of sharing the distributed key information only with particular terminals and having following features.
(1) An amount of communication from the base station to the terminal is small. An amount of data transmission at the base station is small. The service suspending term required until all terminals complete the key sharing is short.
(2) The terminal whose computational capability is not high can achieve the key sharing at high speed. The process in the terminal can be reduced.
In addition, an object of the present invention is to overcome the above problems in the prior art, and to achieve a key sharing method which is secure against the faking attack and the tampering attack by adding a signature function without increase in the communication amount. Also, an object of the present invention is to achieve a key sharing method which is secure against the adaptive chosen ciphertext attack on the basis of the Cramer-Shoup cipher.
However, three following problems exist in the above key sharing method.
(1) It is preferable that the secret information of the terminal should be updated periodically to improve the security. In this case, if the new secret information is distributed to terminal by terminal, an amount of communication and a time needed until the update is completed are increased. In addition, normally the update of the public information is also needed when the secret information are updated. Thus, since the public book and the public information which are saved locally in the terminals are updated, an update time is increased.
(2) In order to exclude continuously the terminals, which have been excluded in the preceding exclusive key sharing, in succeeding all exclusive key sharings, the excluding process is needed every exclusive key sharing.
(3) In order to execute the exclusive key sharing in the system consisting of only the terminal, either all terminals must hold the public information of other terminals or the public book for opening them publicly is needed. Besides, since any terminal can act as the chairman terminal, the method cannot correspond to the case where the chairman terminal must be fixed to a certain terminal in practical use.
In order to overcome the above subjects, the present invention intends to update the secret information in all terminals while suppressing an amount of communication and an update time to the lowest minimum, to exclude continuously the terminals which have been excluded once not to execute the process every exclusive key sharing, to enable each terminal not to hold the public information of all terminals and to eliminate the public book, and to allow only a certain terminal to be appointed as the chairman terminal.
Furthermore, the above exclusive key sharing method contains such a problem that the exponent part employed in the power residue calculation is assumed as about 160 bits and thus the calculation time is long.
In order to overcome further such problem, an object of the present invention is to reduce a size of the exponent part by executing collectively the inverse element calculation, which causes the extension of the exponent part, to thus perform the calculation at high speed in the exclusive key sharing method.
In order to overcome the above subjects, in the present invention, the exclusive key sharing method for the communication system which consists of the base station and N terminals connected to the base station to allow broadcast communication,
wherein the secret keys are S, the prime number which is larger than S and N or the power number of the prime number is p, the measure of (pxe2x88x921) is q, and the number of terminals which can be specified by the base station is 1,
respective terminals i (1xe2x89xa6ixe2x89xa6N) hold secret information Si in secret to satisfy
S=xcexa3xcex(i, xcex9)xc3x97Si (sum of ixcex5xcex9 is calculated)
where Si=S+f1xc3x97i modq (f1 is a non-zero element of GF(q))
xcex(i, xcex9)=Π{L/(Lxe2x88x92i)} (product of Lxcex5xcex9xe2x88x92{i} is calculated)
xcex9 is a set of any two terminals out of the N terminals), the base station holds (S, p, g, S1, . . . , SN),
(1) the base station calculates preparatory information C1=gk modp if the element of GF(p) is g and the non-zero element of GF(q) is k, and
(2) the base station calculates exclusive information C2=g{circumflex over ( )}(kxc3x97Sa modq) modp) based on the secret information Sa of the particular terminal a and then broadcasts it together with the particular terminal number a and the preparatory information C1 to all terminals,
(3) the base station calculates the common key K=g{circumflex over ( )}(kxc3x97S modq) modp) shared with all terminals j (jxe2x89xa0a) except the particular terminal a and
(4) respective terminals j (jxe2x89xa0a) calculate
C1{circumflex over ( )}(Sjxc3x97xcex(j, xcex9) modq)xc3x97C2{circumflex over ( )}(xcex(a, xcex9) modq) modp
to thus obtain the common key K shared with the base station.
According to such configuration, since the key sharing can be achieved by broadcasting from the base station to all terminals, the service suspending term for the key sharing can be reduced and the process in the terminal can be reduced. Therefore, the terminal which has not high computational capability can achieve the key sharing at high speed.
Also, the exclusive key sharing method for the communication system which consists of N terminals (N is an integer of more than 2) connected mutually to allow broadcast communication is constructed such that the secret keys are S, the prime number which is larger than S and N or the power number of the prime number is p, the measure of (pxe2x88x921) is q, and the particular terminal number which can be specified by the chairman terminal xcfx86 (to which any terminal can be appointed) d (1xe2x89xa6dxe2x89xa6Nxe2x88x921),
respective terminals i (1xe2x89xa6ixe2x89xa6N) hold secret information Si in secret to satisfy
S=xcexa3xcex(i, xcex9)xc3x97Si (sum of ixcex5xcex9 is calculated)
xcex(i, xcex9)=Π{L/(Lxe2x88x92i)} (product of Lxcex5xcex9xe2x88x92{i} is calculated)
Si=S+f1xc3x97i1+ . . . , +fdxc3x97id modq
(where f1, . . . , fd are d elements of GF(q), fdxe2x89xa00, and xcex9 is a set of any (d+1) terminals out of the N terminals), and can use the public key of the system
y=gs modp,
public information
y1=gS1 modp, y2=gS2 modp, . . . , yN=gSN modp,
the prime number p, the measure q, and the element g, and
(1) the chairman terminal generates arbitrarily the non-zero element k of GF(q) and then calculates exclusive information
C2i1=yi1k modp, . . . , C2id=yidk modp
based on the public information yi1, . . . , yid of the d terminals i1, . . . , id,
(2) the chairman terminal calculates a signature
xe2x80x83Z=C2i1xc3x97 . . . xc3x97C2idxc3x97(xe2x88x92Sxcfx86)+k modq
by using own secret information Sxcfx86, and broadcasts the signature Z together with the exclusive information C2i1, . . . , C2id, the particular terminal numbers i1, . . . , id and own terminal number xcfx86 to all terminals,
(3) the chairman terminal calculates a common key
K=yk modp,
(4) the respective terminals j (jxe2x89xa0i1, . . . , id, xcfx86) calculate
C1=gzxc3x97yxcfx86{circumflex over ( )}(C2i1xc3x97 . . . xc3x97C2id modq) modp
(if a signer is surely the chairman terminal xcfx86 and also the signature Z, the exclusive information C2i1, . . . , C2id, the particular terminal numbers i1, . . . , id, and the terminal number xcfx86 of the chairman terminal are not tampered, C1=gk modp is calculated) by using the public information y, of the chairman terminal,
(5) the respective terminals j calculate xcex(j, xcex9) and xcex(i1, xcex9), . . . , (id, xcex9) where xcex9={j, i1, . . . , id}, and calculate C1{circumflex over ( )}(Sjxc3x97xcex(j, xcex9) modq)xc3x97C2i1{circumflex over ( )}(xcex(i1, xcex9) modq)xc3x97 . . . xc3x97C2id{circumflex over ( )}(xcex(id, xcex9) modq) modp by using the C1, the exclusive information C2i1, . . . , C2id, and own secret information Sj to thus obtain the common key K.
According to such configuration, only the particular terminal can be excluded by a small amount of communication, other terminals can share the distributed key information, and the distributed key information can be shared with the particular terminals only.
Moreover, in order to overcome the above subjects, in the present invention, the exclusive key sharing method for a communication system which consists of the base station and N terminals (N is an integer of more than 2) connected to the base station to allow broadcast communication is constructed such that the secret keys are S, the prime number which is larger than S and N or the power number of the prime number is p, the measure of (pxe2x88x921) is q, and the number of terminals which can be specified by the base station (referred to as the xe2x80x9cparticular terminal numberxe2x80x9d hereinafter) is 1,
respective terminals i (1xe2x89xa6ixe2x89xa6N) hold secret information Si in secret to satisfy
S=xcexa3xcex(i, xcex9)xc3x97Si (sum of ixcex5xcex9 is calculated)
(where Si=S+f1xc3x97i modq (f1 is a non-zero element of GF(q)), xcex(i, xcex9)=Π{L/(Lxe2x88x92i)} (product of Lxcex5xcex9xe2x88x92{i} is calculated), and xcex9 is a set of any two terminals out of the N terminals), and
the base station holds (S, p, g, S1, . . . , SN),
(1) the base station calculates preparatory information
C1=gk modp
where an element of GF(p) is g and a non-zero element of GF(q) is k,
(2) the base station calculates exclusive information
C2=g{circumflex over ( )}(kxc3x97Sa modq) modp,
based on the secret information Sa of the particular terminal a, and broadcasts the exclusive information together with the particular terminal number a and the preparatory information C1 to all terminals, and
(3) the base station calculates a common key
K=g{circumflex over ( )}(kxc3x97S modq) modp
which is shared with all terminals j (jxe2x89xa0a) except the particular terminal a,
(4) the respective terminals j (jxe2x89xa0a) calculate a product
C1{circumflex over ( )}(Sjxc3x97xcex(j, xcex9) modq)xc3x97C2{circumflex over ( )}(xcex(a, xcex9) modq) modp
of a power residue value of C1
C1{circumflex over ( )}(Sjxc3x97xcex(j, xcex9) modq) modp
which uses a product of Sj and xcex(j, xcex9) to the modulus q as an exponent and a power residue value of C2
C2{circumflex over ( )}(xcex(a, xcex9) modq) modp
which uses xcex(a, xcex9) calculated to the modulus p as the exponent by using the preparatory information C1, the exclusive information C2, and own secret information Sj to thus obtain the common key K which is shared with the base station, and
(i) the base station generates arbitrarily the non-zero element e of GF(q), and broadcasts the e to all terminals,
(ii) the base station calculates the new element
gxe2x80x2=g1/e modq modp
and replaces it with the managed element g,
(iii) the respective terminals i calculate the new secret information
Sixe2x80x2=Sixc3x97e modq
(at this time, (gxe2x80x2)Sixe2x80x2 modp=(g)Si modp is satisfied).
According to such configuration, since an amount of communication required for the base station is small such as the e and the public information other than the system parameter element g are not changed, such an advantage can be achieved that update of the secret information can be performed at high speed.
Also, the exclusive key sharing method for the communication system which consists of N terminals (N is an integer of more than 2) connected mutually to allow broadcast communication is constructed such that
(i) the system manager generates arbitrarily the non-zero element e of GF(q), and broadcasts the e to all terminals,
(ii) the system manager calculates the new element
gxe2x80x2=g1/e modq modp
and replaces the managed element g with it, and
(iii) the respective terminals i calculate the new secret information
Sixe2x80x2=Sixc3x97e modq
(at this time, (gxe2x80x2)Sixe2x80x2 modp=(g)Si modp is satisfied).
According to such configuration, since an amount of communication required for the system manager is small such as the e and the public information other than the system parameter element g are not changed, such an advantage can be achieved that update of the secret information can be performed at high speed.
Also, the exclusive key sharing method for the communication system which consists of the base station and the N terminals (N is an integer of more than 2) connected to the base station to allow broadcast communication is constructed such that
(i) the base station generates arbitrarily the non-zero element e of GF(q), and broadcasts the encrypted e encrypted by using the common key K to all terminals,
(ii) the base station calculates the new element
gxe2x80x2=g1/e modq modp
and replaces it with the managed element g, and
(iii) the respective terminals i decrypt the encrypted e by using the common key K, and calculate the new secret information
Sixe2x80x2=Sixc3x97e modq
According to such configuration, since the secret information of the terminals can be updated by using the random number which is distributed using the common key which is shared by the exclusive key sharing, the excluded terminal cannot be restored in the succeeding exclusive key sharing.
Also, the exclusive key sharing method for a communication system which consists of the N terminals (N is an integer of more than 2) connected mutually to allow broadcast communication is constructed such that
(i) the chairman terminal generates arbitrarily the non-zero element e of GF(q), and broadcasts the encrypted e which is encrypted by using the common key K to all terminals,
(ii) the chairman terminal calculates the new element
gxe2x80x2=g1/e modq modp
and replaces it with the element g,
(iii) the respective terminals j decrypt the encrypted e by using the common key K, and calculate the new secret information
Sixe2x80x2=Sixc3x97e modq
According to such configuration, since the secret information of the terminals can be updated by using the random number which is distributed using the common key which is shared by the exclusive key sharing, the excluded terminal cannot be restored in the succeeding exclusive key sharing.
Also, the exclusive key sharing method for the communication system which consists of N terminals (N is an integer of more than 2) connected mutually to allow broadcast communication is constructed such that the secret keys are S, the prime number which is larger than S and N or the power number of the prime number is p, the measure of (pxe2x88x921) is q, elements of GF(p) are g, and the particular terminal number which can be specified by the chairman terminal b is 1,
respective terminals i (1xe2x89xa6ixe2x89xa6N) hold secret information Si in secret to satisfy
S=xcexa3xcex(i, xcex9)xc3x97Si (sum of ixcex5xcex9 is calculated)
(where Si=S+f1xc3x97i modq (f1 is a non-zero element of GF(q)), xcex(i, xcex9)=Π{L/(Lxe2x88x92i)} (product of Lxcex5xcex9xe2x88x92{i} is calculated), and xcex9 is a set of any two terminals out of the N terminals), and
the chairman terminal b can use the public key for all terminals
y=gS modp
and the public information
y1=gS1 modp, y2=gS2 modp, . . . , yN=gSN modp,
(1) the chairman terminal b generates the non-zero element k of GF(q), and calculates the preparatory information
C1=gk modp,
(2) the chairman terminal b calculates the exclusive information
C2=yak modp
based on the public information ya of the particular terminal a, and broadcasts the exclusive information together with the particular terminal number a and the preparatory information C1 to all terminals, and
(3) the chairman terminal b calculates the common key
K=yk modp,
(4) the respective terminals j (jxe2x89xa0a, b) calculate xcex(j, xcex9) and xcex(a, xcex9) where xcex9={j, a}, and calculate
C1{circumflex over ( )}(Sjxc3x97xcex(j, xcex9) modq)xc3x97C2{circumflex over ( )}(xcex(a, xcex9) modq) modp
by using the preparatory information C1, the exclusive information C2, and own secret information S, to thus obtain the common key K.
According to such configuration, since the terminals except the chairman terminal are not requested to hold the public information of other terminals and only the chairman terminal can use the public information of other terminals, such an advantage can be achieved that other terminals cannot be designated as the chairman terminal.
Further, in order to overcome the above subjects, in the present invention, the exclusive key sharing method for the communication system which consists of N terminals (N is an integer of more than 2) connected mutually to allow broadcast communication is constructed such that the secret keys are S, the prime number which is larger than S and N or the power number of the prime number is p, the measure of (pxe2x88x921) is q, elements of GF(p) are g, and the particular terminal number which can be specified by the chairman terminal xcfx86 is d (1xe2x89xa6d less than Nxe2x88x921), respective terminals i (1xe2x89xa6ixe2x89xa6N) hold secret information Si in secret to satisfy
S=xcexa3xcex(i, xcex9)xc3x97Si
(where f1, . . . , fd are d elements of GF(q), fdxe2x89xa00), xcex(i, xcex9)=Π{L/(Lxe2x88x92i)} (product of Lxcex5xcex9xe2x88x92{i} is calculated), and xcex9 is a set of any (d+1) terminals out of the N terminals), the respective terminals i and the chairman terminal xcfx86 can use the public key of the system
y=gS modp,
the public information
y1=gS1 modp, y2=gS2 modp, . . . , yN=gSN modp,
and the p, q, and g,
(1) the chairman terminal calculates the preparatory information
C1=gk modp (k is a non-zero element of GF(q)),
(2) the chairman terminal calculates the exclusive information
C2i1=yi1{circumflex over ( )}(kxc3x97xcex(i1, xcex1) modq) modp, . . . , C2id=id{circumflex over ( )}(kxc3x97xcex(id, xcex1) modq) modp
based on a set xcex1 of the d particular terminals i1, . . . , id, xcex(i1, xcex1), . . . , xcex(id, xcex1), and the public information yi1, . . . , yi1, and broadcasts the exclusive information C2i1, . . . , C2id together with the preparatory information C1 and the particular terminal number i1, . . . , id to all terminals, and
(3) the chairman terminal calculates the common key
K=yk modp,
(4) the respective terminals j (jxe2x89xa0i1, . . . , id, xcfx86) calculate
xcex(j, xcex9j), xcex(i1, {j, i1}), . . . , xcex(id, {j, id}), j where xcex9j={j, i1, . . . , id} and
Tj={Π(jxe2x88x92L)}/(product of Lxcex5xcex9xe2x88x92{i} is calculated),
and calculate cession keys
Ki=C1{circumflex over ( )}(Sjxc3x97xcex(j, xcex9j)xc3x97Tj modq)xc3x97C2i1{circumflex over ( )}(xcex(i1, {j, i1})xc3x97Tj modq)xc3x97 . . . xc3x97C2id{circumflex over ( )}(xcex(id, {j, id})xc3x97Tj modq) modp
by using the preparatory information C1, the exclusive information C2i1, . . . , C2id, and own secret information Sj, and calculates
Kj{circumflex over ( )}(1/Tj modq) modp
to thus obtain the common key.
According to such configuration, the operation can be performed at high speed by reducing a size of the exponent part and thus the key sharing can be implemented at high speed. Also, since the chairman terminal bears the calculation of the terminal side, respective terminals can perform the key sharing at high speed.
In the present invention, higher speed of the exclusive key sharing method is intended by using the following approach. Expansion in size of the modulus due to the inverse element of the exponent part can be prevented by calculating collectively the inverse elements of the exponent part in the power residue calculation of the exclusive information of respective terminals in the key sharing at the end. The same values exist as the coefficient concerning the excluded terminal number in the exponent part in the power residue calculation of the exclusive information executed by respective terminals in the key sharing. Therefore, the exponent part in the key sharing can be reduced if the base station or the chairman terminal calculates previously this value into the power residue value in the exclusive information.
There is the case where a negative value of the exponent part is present in the power residue calculation of the exclusive information performed by the respective terminals at the time of key sharing. In this case, the exponent part is expanded up to the size of the modulus even by the above countermeasure. Therefore, in the case of the negative exponent part, the reduction effect can also be achieved if the respective terminals calculate in advance the inverse elements of the exclusive information and then power-residue-calculate the absolute value of the exponent part into the inverse elements of the exclusive information.